# 1.随机初始化 k 个集群中心。
# 2.将每个数据点分配给最近的集群中心。
# 3.将聚类中心更新为聚类中点的平均值。
# 4.重复步骤 2 和 3，直到收敛（集群中心不变）。

import random
import numpy as np

def k_means(data, k, max_iterations=100):
    n = len(data)
    indices = random.sample(range(n), k)
    centers = [data[i] for i in indices]

    for _ in range(max_iterations):
        clusters = [[] for _ in range(k)]
        for point in data:
            distances = [np.linalg.norm(np.array(point) - np.array(center)) for center in centers]
            cluster_index = np.argmin(distances)
            clusters[cluster_index].append(point)

        new_centers = []
        for cluster in clusters:
            if cluster:
                new_centers.append(np.mean(cluster, axis=0).tolist())
            else:
                new_centers.append(data[random.randint(0, n - 1)])

        if np.allclose(centers, new_centers):
            break
        centers = new_centers

    return clusters, centers

points = [
    [1.0, 2.0], [1.5, 1.8], [5.0, 8.0],
    [8.0, 8.0], [1.0, 0.6], [9.0, 11.0],
    [8.0, 2.0], [10.0, 2.0], [9.0, 3.0]
]

num_clusters = 3
clusters, centers = k_means(points, num_clusters)


print("Cluster Centers:")
for i, center in enumerate(centers):
    print(f"Cluster {i + 1} Center: {center}")

print("\nCluster Assignments:")
for i, cluster in enumerate(clusters):
    print(f"Cluster {i + 1}: {cluster}")
